package personal.leil.learning.select;

import personal.leil.learning.utils.ArrayUtils;

/**
 * 选择排序
 * <p>
 * 选择排序算法具体实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2023-12-29
 */
public class SelectSort {

    /**
     * 选择排序
     *
     * @param arr 要排序的源数组
     */
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = findMin(arr, i, arr.length - 1);
            ArrayUtils.swap(arr, i, minIndex);
        }
    }

    /**
     * 从给定的数组范围内查找最小值
     *
     * @param arr 原数组
     * @param l   左边界
     * @param r   右边界
     * @return 最小值索引
     */
    public static int findMin(int[] arr, int l, int r) {
        int minIndex = l;
        for (int i = l; i <= r; i++) {
            if (arr[minIndex] > arr[i]) {
                minIndex = i;
            }
        }
        return minIndex;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateRandomArr(20);
        System.out.println("before sort:");
        ArrayUtils.printArr(arr);
        selectSort(arr);
        System.out.println("after sort:");
        ArrayUtils.printArr(arr);
    }
}
